#include <iostream>
#include <queue>
#include <cstring>
#include <vector>

using namespace std;

typedef pair<int, int> PII;
const int N = 2555, M = 2.1e5 + 10;

int n, m, k;
int h[N], e[M], w[M], ne[M], id;
int dist[N];
bool st[N];

void add(int a, int b, int c)
{
	id++;
	e[id] = b; w[id] = c; ne[id] = h[a]; h[a] = id;
}

void dijkstra()
{
	memset(dist, 0x3f, sizeof dist);
	priority_queue<PII, vector<PII>, greater<PII>> heap;
	heap.push({0, 1});
	dist[1] = 0;
	
	while(heap.size())
	{
		int x = heap.top().second; heap.pop();
		if(st[x]) continue;
		st[x] = true;
		
		for(int i = h[x]; i; i = ne[i])
		{
			int y = e[i], z = w[i];
			if(dist[x] + z < dist[y])
			{
				dist[y] = dist[x] + z;
				heap.push({dist[y], y});
			}
		}
	}
}

int main()
{
	cin >> n >> m >> k;
	for(int i = 1; i <= m; i++)
	{
		int a, b, c; cin >> a >> b >> c;
		add(a, b, c); add(b, a, c);
		for(int j = 1; j <= k; j++)
		{
			int x = a + n, y = b + n;
			add(x, y, c); add(y, x, c);
			add(a, y, c / 2); add(b, x, c / 2);
			a = x; b = y;
		}
	}
	
	dijkstra();
	
	int ret = 1e9;
	for(int i = 0; i <= k; i++)
		ret = min(ret, dist[n + i * n]);
	cout << ret << endl;
	
	return 0;
}




















